import printer.BinaryTreeInfo;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @program: LoveDataStructures1
 * @description: [用一句话描述此类]
 * @author: wxc
 * @create: 2021-07-26 22:52
 **/
public abstract class BinaryTree<E> implements BinaryTreeInfo<BinaryTree.Node<E>> {
    protected int size;
    protected Node<E> root;

    public BinaryTree() {
    }

    protected static class Node<E> {
        E element;
        Node<E> left;
        Node<E> right;
        Node<E> parent;

        public Node(E element, Node<E> left, Node<E> right, Node<E> parent) {
            this.element = element;
            this.left = left;
            this.right = right;
            this.parent = parent;
        }

        public boolean isLeaf() {
            return this.left == null && this.right == null;
        }

        public boolean hasFullChild() {
            return this.left != null && this.right != null;
        }
    }

    /*
     * @param
     * @author wxc
     * @return true表示停止遍历
     * @Description: 外部传入对每个结点的处理方式
     */
    public static abstract class Visitor<E> {
        boolean stop;

        abstract boolean visit(Node<E> node);
    }

    public int getSize() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void clear() {
        size = 0;
        root = null;
    }

    public void preOrder() {
        preOrder(root, null);
    }

    public void preOrder(Visitor<E> visitor) {
        preOrder(root, visitor);
    }

    private void preOrder(Node<E> node, Visitor<E> visitor) {
        // 要想递归停止 进行两次校验
        // 1: if (node == null || visitor.stop) return;
        // 2: if(visitor.stop) return; 注意位置
        if (node == null || (visitor != null && visitor.stop)) return;
        if (visitor != null) {
            if (visitor.stop) return;
            visitor.stop = visitor.visit(node);
        } else visit(node);
        preOrder(node.left, visitor);
        preOrder(node.right, visitor);
    }

    public void infixOrder() {
        infixOrder(root, null);
    }

    public void infixOrder(Visitor<E> visitor) {
        infixOrder(root, visitor);
    }

    private void infixOrder(Node<E> node, Visitor<E> visitor) {
        if (node == null || (visitor != null && visitor.stop)) return;
        infixOrder(node.left, visitor);
        if (visitor != null) {
            if (visitor.stop) return;
            visitor.stop = visitor.visit(node);
        } else visit(node);
        infixOrder(node.right, visitor);
    }

    public void postOrder() {
        postOrder(root, null);
    }

    public void postOrder(Visitor<E> visitor) {
        postOrder(root, visitor);
    }

    private void postOrder(Node<E> node, Visitor<E> visitor) {
        if (node == null || (visitor != null && visitor.stop)) return;
        postOrder(node.left, visitor);
        postOrder(node.right, visitor);
        if (visitor != null) {
            if (visitor.stop) return;
            visitor.stop = visitor.visit(node);
        } else visit(node);
    }

    private void visit(Node<E> node) {
        System.out.print(node.element.toString() + "->");
    }

    public void levelOrder() {
        levelOrder(root, null);
    }

    public void levelOrder(Visitor<E> visitor) {
        levelOrder(root, visitor);
    }

    private void levelOrder(Node<E> node, Visitor<E> visitor) {
        if (node == null) return;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(node);
        Node<E> tempNode;
        while (queue.size() > 0) {
            tempNode = queue.poll();
//            System.out.print(tempNode.element.toString() + "->");
            // 和自定义Comparator接口很想,外面决定每个结点的处理方式
            if (visitor != null) {
                visitor.stop = visitor.visit(tempNode);
                if (visitor.stop) return;
            } else visit(node);

            if (tempNode.left != null) queue.offer(tempNode.left);
            if (tempNode.right != null) queue.offer(tempNode.right);
        }
    }

    private int height(Node<E> node) {
        if (node == null) return 0;
        return 1 + Math.max(height(node.left), height(node.right));
    }

    /*
     * @param
     * @author wxc
     * @return
     * @Description: 计算树的高度 循环 利用层序遍历
     */
    private int height2(Node<E> node) {
        if (node == null) return 0;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(node);
        Node<E> tempNode;
        int height = 0;
        // 每层结点个数
        int levelSize = 1;
        while (queue.size() > 0) {
            tempNode = queue.poll();
            levelSize--;

            if (tempNode.left != null) queue.offer(tempNode.left);
            if (tempNode.right != null) queue.offer(tempNode.right);
            // 如果为0则说明下一层结点全部在队列中，个数就是队列长度
            if (levelSize == 0) {
                levelSize = queue.size();
                // 增加heihgt,增加的是该层
                height++;
            }
        }
        return height;
    }

    public int height() {
        return height2(root);
//        return height(root);
    }

//    // 是否是完全二叉树
//    public boolean isComplete() {
//        if (root == null) return false;
//        Queue<Node<E>> queue = new LinkedList<>();
//        queue.offer(root);
//        Node<E> tempNode;
//        boolean leaf = false;
//        while (queue.size() > 0) {
//            tempNode = queue.poll();
//            if (leaf && !tempNode.isLeaf()) return false;
//            if (tempNode.hasFullChild()) {
//                queue.offer(tempNode.left);
//                queue.offer(tempNode.right);
//            } else if (tempNode.left == null && tempNode.right != null) return false;
//                // 左子结点不为空右结点为空 || 都为空 => 后面的结点都是叶子结点
//            else {
//                leaf = true;
//                if (tempNode.left != null) queue.offer(tempNode.left);
//            }
//        }
//        return true;
//    }

    // 重构
    public boolean isComplete() {
        if (root == null) return false;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        Node<E> tempNode;
        boolean leaf = false;
        while (queue.size() > 0) {
            tempNode = queue.poll();
            if (leaf && !tempNode.isLeaf()) return false;

            if (tempNode.left != null) {
                queue.offer(tempNode.left);
            } else if (tempNode.right != null) return false;

            if (tempNode.right != null) {
                queue.offer(tempNode.right);
            } else leaf = true;
        }
        return true;
    }

    /*
     * @param
     * @author wxc
     * @return
     * @Description: 获得某一个二叉树中序遍历的前驱节点 连上数据结构 P120
     */
    protected Node<E> getPredecessor(Node<E> node) {
        if (node == null) return null;
        // 说明是根结点
        if (node.left == null && node.parent == null) return null;
        // 一直往上走，如果父结点的是父父结点的右子结点,那么pre就是父父结点
        // 具体可以看视频
        Node<E> pre = null;
        if (node.left == null && node.parent != null) {
            pre = node;
            while (pre != null && pre.parent != null) {
                if (pre.parent.right == pre) return pre.parent;
                pre = node.parent;
            }
        }
        // 先往左走 再一直往右走
        else if (node.left != null) {
            pre = node.left;
            while (pre.right != null) pre = pre.right;
            return pre;
        }
        return pre;
    }

    /*
     * @param
     * @author wxc
     * @return
     * @Description:获得某一个二叉树中序遍历的后继节点 连上数据结构 P120
     */
    protected Node<E> getSuccessor(Node<E> node) {
        if (node == null) return null;
        // 说明是根结点
        if (node.right == null && node.parent == null) return null;
        // 一直往上走，如果父结点的是父父结点的右子结点,那么pre就是父父结点
        // 具体可以看视频
        Node<E> pre = null;
        if (node.right == null && node.parent != null) {
            pre = node;
            while (pre != null && pre.parent != null) {
                if (pre.parent.left == pre) return pre.parent;
                pre = node.parent;
            }
        }
        // 先往右 再一直往左
        else if (node.right != null) {
            pre = node.right;
            while (pre.left != null) pre = pre.left;
            return pre;
        }
        return pre;
    }

    @Override
    public Node<E> root() {
        return root;
    }

    @Override
    public String string(Node<E> node) {
        String parentStr = node.parent == null ? "null" : node.parent.element.toString();
        return node.element.toString() + "_parent(" + parentStr + ")";
    }

    @Override
    public Node<E> right(Node<E> node) {
        return node.right;
    }

    @Override
    public Node<E> left(Node<E> node) {
        return node.left;
    }
}
